from queue import *


def spfa():
    q = Queue()
    q.put(1)
    b[1] = True
    dis[1] = 0
    while not q.empty():
        x = q.get()
        b[x] = False
        for to, len in graph[x]:
            if dis[x] + len < dis[to]:
                dis[to] = dis[x] + len
                if b[to] == False:
                    q.put(to)
                    b[to] = True


INF = int(1e15)
n, m = map(int, input().split())
dis = [INF] * (n + 10)
b = [False] * (n + 10)
graph = [[] for _ in range(n + 10)]
for i in range(m):
    x, y, len = map(int, input().split())
    graph[x].append((y, len))
spfa()
for i in range(1, n + 1):
    if(dis[i] == INF):
        print("-1", end=" ")
    else:
        print(dis[i], end=" ")
